package main

import (
	"fmt"
	"math/rand"
	"time"
)

// ==========排序==========
// 排序分为内部排序和外部排序
// 1、内部排序(所有数据加载到内存排序)
//    - 交换式排序: 冒泡排序、快速排序
//    - 选择式排序
//    - 插入式排序
// 2、外部排序(借助外部存储)
//    - 合并排序
//    - 直接合并排序

func RandSlice(n int) []int {
	rand.Seed(time.Now().UnixNano())
	var array []int
	for i := 0; i < n; i++ {
		array = append(array, rand.Intn(50))
	}
	return array
}

func BubbleSort(slice *[]int) {
	/*
		每一轮排序过后, 将大的数推向了数组的尾部, 假设数据共有n个数据, 那么,
		第一轮循环比较n - 1次,
		第二轮循环比较n - 2次,
		第三轮循环比较n - 3次,
		...
		最后一次比较第一和第二个数一次, 完毕
	*/
	length := len(*slice)
	for i := 0; i < length-1; i++ {
		for j := 0; j < length-1-i; j++ {
			if (*slice)[j] > (*slice)[j+1] {
				(*slice)[j], (*slice)[j+1] = (*slice)[j+1], (*slice)[j]
			}
		}
	}
}

func QuickSort(slice []int, left, right int) {
	temp := slice[left]
	p := left
	i, j := left, right
	for i <= j {
		for j >= p && slice[j] >= temp {
			j--
		}
		if j >= p {
			slice[p] = slice[j]
			p = j
		}
		if slice[i] <= temp && i <= p {
			i++
		}
		if i <= p {
			slice[p] = slice[i]
			p = i
		}
	}
	slice[p] = temp
	if p-left > 1 {
		QuickSort(slice, left, p-1)
	}
	if right-p > 1 {
		QuickSort(slice, 0, len(slice)-1)
	}
}

func main() {
	slice := RandSlice(20)
	fmt.Println(slice)
	BubbleSort(&slice)
	fmt.Println(slice)
}
